﻿<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>MPI实现矩阵乘法-简单</title>
  <link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>

<body class="stackedit">
  <div class="stackedit__html"><h1 id="mpi实现矩阵乘法-简单">MPI实现矩阵乘法-简单</h1>
<p><strong>计试61 张翀 2140506063</strong></p>
<h2 id="题目">题目</h2>
<p>使用MPI实现矩阵乘法。此处为了简单，只需使用MPI实现<code>n*n</code>方阵之间的乘法。</p>
<h2 id="思路">思路</h2>
<p>主进程将第一个相乘矩阵按照行分割成数块，然后分发给子进程；紫禁城将获得的一块矩阵和完整的第二个相乘矩阵相乘，计算得到对应的一块计算结果，返回主进程；主进程收集计算结果，计算过程结束。</p>
<h2 id="代码">代码</h2>
<p>在这里，我们主要使用<code>Scatter-Gather</code>和<code>BCast</code>两条指令做数据的分发和接收。</p>
<h3 id="scatter-gather">Scatter-Gather</h3>
<p>对于第一个相乘矩阵A，每个进程获得A的各不相同的一部分，所以用<code>Scatter</code>分发，用<code>Gather</code>接收比较合适。<br>
以下是<code>MPI_Scatter</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Scatter</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span><span class="token operator">*</span> send_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> send_count<span class="token punctuation">,</span>
    MPI_Datatype send_datatype<span class="token punctuation">,</span>
    <span class="token keyword">void</span><span class="token operator">*</span> recv_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> recv_count<span class="token punctuation">,</span>
    MPI_Datatype recv_datatype<span class="token punctuation">,</span>
    <span class="token keyword">int</span> root<span class="token punctuation">,</span>
    MPI_Comm communicator
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>对于需要分发的消息，需要指定源数据、数据类型和广播消息的进程，并指定发送给每个进程的数据量，以及每个进程接收数据的位置指针。执行这条命令之后，按照进程号顺序，指定数据会分发给每一个进程。<br>
以下是<code>MPI_Gather</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Gather</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span><span class="token operator">*</span> send_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> send_count<span class="token punctuation">,</span>
    MPI_Datatype send_datatype<span class="token punctuation">,</span>
    <span class="token keyword">void</span><span class="token operator">*</span> recv_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> recv_count<span class="token punctuation">,</span>
    MPI_Datatype recv_datatype<span class="token punctuation">,</span>
    <span class="token keyword">int</span> root<span class="token punctuation">,</span>
    MPI_Comm communicator
<span class="token punctuation">)</span>
</code></pre>
<p>参数基本相同，从部分数据变量中读取数据，按照进程号顺序被目标进程收集。<br>
注意：使用<code>Scatter</code>分配数据后，每个进程分配的部分矩阵具有完全相等的规模。因此。记<code>comm_sz</code>为进程数，矩阵的维度需要是<code>comm_sz</code>的倍数。我们将矩阵的维度扩展到<code>comm_sz</code>的倍数，多余的部分用0填充，保证正确性。</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token comment">// 维度数调整为进程数的倍数</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>n <span class="token operator">%</span> comm_sz <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
    n <span class="token operator">-</span><span class="token operator">=</span> n <span class="token operator">%</span> comm_sz<span class="token punctuation">;</span>
    n <span class="token operator">+</span><span class="token operator">=</span> comm_sz<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre>
<p>另外，主进程也要参与数据分发。</p>
<h3 id="broadcast">Broadcast</h3>
<p>对于第二个相乘矩阵B，每个进程获得完整的B，所以用<code>BCast</code>分发比较合适。<br>
以下是<code>MPI_Bcast</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Bcast</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span> <span class="token operator">*</span> data_p<span class="token punctuation">;</span>
    <span class="token keyword">int</span> count<span class="token punctuation">;</span>
    MPI_Datatype datatype<span class="token punctuation">;</span>
    <span class="token keyword">int</span> source_proc<span class="token punctuation">;</span>
    MPI_Comm comm<span class="token punctuation">;</span>
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p><code>MPI_Bcast</code>要求所有进程保有同一个变量指针，然后从一个进程的对应位置复制数据，拷贝到其他进程。</p>
<h3 id="程序代码">程序代码</h3>
<p>为了方便测试时间，设计函数<code>matGene</code>生成指定大小的矩阵，<code>vecGene</code>生成指定大小的向量，生成矩阵之后求乘积，再输出结果。设计代码如附件所示。</p>
<h2 id="实验结果">实验结果</h2>
<p>使用如下命令编译并执行：<code>mpicxx main.cpp &amp;&amp; mpiexec -n num_processes ./a.out mat_dim</code>，执行可执行文件时带的两个参数分别是矩阵维度和使用的进程数。<br>
在一台8核机器上测试，测试时间如下：</p>

<table>
<thead>
<tr>
<th align="center">线程数</th>
<th align="center">1</th>
<th align="center">2</th>
<th align="center">4</th>
<th align="center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">256</td>
<td align="center">0.0665398</td>
<td align="center">0.0345254</td>
<td align="center">0.0137167</td>
<td align="center">0.00820518</td>
</tr>
<tr>
<td align="center">512</td>
<td align="center">1.65359</td>
<td align="center">0.827351</td>
<td align="center">0.447173</td>
<td align="center">0.237067</td>
</tr>
<tr>
<td align="center">1024</td>
<td align="center">44.327</td>
<td align="center">22.509</td>
<td align="center">11.403</td>
<td align="center">6.59968</td>
</tr>
</tbody>
</table><p>表格中最左侧一栏为测试时矩阵维度，表格中时间单位为秒。</p>
<p>测试加速比如下：</p>

<table>
<thead>
<tr>
<th align="center">线程数</th>
<th align="center">1</th>
<th align="center">2</th>
<th align="center">4</th>
<th align="center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">256</td>
<td align="center">1</td>
<td align="center">1.9273</td>
<td align="center">4.8510</td>
<td align="center">8.1095</td>
</tr>
<tr>
<td align="center">512</td>
<td align="center">1</td>
<td align="center">1.9987</td>
<td align="center">3.6979</td>
<td align="center">6.9752</td>
</tr>
<tr>
<td align="center">1024</td>
<td align="center">1</td>
<td align="center">1.9693</td>
<td align="center">3.8873</td>
<td align="center">6.7165</td>
</tr>
</tbody>
</table><p>表格中最左侧一栏为测试时矩阵维度。</p>
<p>由上述结果，发现如下两点：</p>
<ul>
<li>矩阵乘法的算法是O(n<sup>3</sup>)的，但此处的运行时间增长却是O(n<sup>5</sup>)的，这里目前还不知道原因是什么，可能是算法设计时的缺陷。</li>
<li>通过多进程并行执行程序，程序确实能获得对应的加速比。本次实验使用较大规模的数据，相对误差较小，基本体现了正确的加速比。</li>
</ul>
</div>
</body>

</html>
